This invention relates to instruction processing in an electronic digital computer. More particularly, this invention relates to an apparatus and a method in a digital computer which allows greatly improved program branching for a specific class of programs, and is to be distinguished from similar inventions directed to the problem of anticipating or reducing the delay between execution of the steps in the user class of programs.
A user language computer program is typically written in a high level language easily readable by the program's user. Before the computer can act on the program however, the translator of the computer must convert the individual components of the user language program into the machine level language of the computer. The translator does this by executing a system routine, known as a compiler. The compiler, like any other program, includes sets of sequential instructions connected by one or more branch conditions (or, by analogy, program paths connected by one or more junctions). Speed of performance for state of the art digital computers in performing uninterrupted or non-branching instruction sets is very good. In any digital computer program however, branching is a virtual necessity. Furthermore, due to the necessity of resolving branch conditions, the instruction sequencing mechanism of the computer would not know which set of instructions to prepare next.
Each compiler instruction is identified by its position in the program, each position having a program address (PA). After executing each of the sequential instructions in a given set, a branch point or junction is reached. Here the compiler, like any other program, must execute one or more "overhead" instructions in order to obtain the program address of the first instruction to be performed in the next set of instructions (i.e., the effective branch address, or the next program address or NPA). The instruction sequencing mechanism, a register known as a program counter (PC), stores the current program address. Each compiler branch point typically requires the translator to perform several "overhead" steps, and it is not uncommon for the translator to devote from twenty to thirty percent of its time to executing the steps required to evaluating which branch condition is met or, in other words, determining the NPA after a branch point. From 1 to 14 microseconds per branch condition may be required using state of the art translators.
In the prior art, the vast majority of branch point conditions require comparing a value stored in a given translator register, W, with a literal value (e.g. "IF", "THEN", "ELSE", +, -, *. /, etc.). Each possible case W = "IF", "W" ="THEN", etc., defines a different NPA. For each comparison, the following typical operations must be performed:
______________________________________ 100 LOAD W 101 SUBTRACT "IF" 102 JUMP ZERO TO W = "IF" NPA 103 TRY NEXT COMPARISON o o 0 o o o ______________________________________
Only after the value of translator register W has either successfully compared with a literal value (e.g., "IF") of one of the compiler branch conditions or defaulted in a favorable comparison, and the program counter has the address of the first instruction in the next set of instructions, is the translator able to continue with the useful portion of the compilation of the user program.